//
//  main.cpp
//  十字链表
//
//  Created by 刘晨 on 2018/11/24.
//  Copyright © 2018 刘晨. All rights reserved.
//
/*
 在开发中遇到的问题：
 1:在添加结点的时候，开始时候要查找结点在数组中的位置，若是没有那就添加，找结点位置函数返回值是-1；，我遇到的问题是在添加新结点的时候结点的位置没有更新这个结点在数组中的位置，讲-1添加进去了。
*/
#include <iostream>
using namespace std;
#define  MAXSIZE 100
#define dataType char
typedef struct node{
    int tail;//弧尾在数组中的位置
    int head;//弧首在数组中的位置
    node *tailNode;//以这个顶点为弧尾的下一条的位置
    node *headNode;//以这个顶点为弧头的下一天的位置
    int info;//权重
}node;
typedef struct Box{
    dataType data;
    node *in;//入度
    node *out;//出读
}Box;
class Graph{
private:
    Box base[MAXSIZE];
    int vertexNum;
    int edgeNum;
#pragma private mathod
    int locate(dataType x);//定位
public:
    void init(int vertexNum,int edgeNum);//初始化结点个数和边的个数
    void create();//创建图
    int indegree(dataType x);//入度
    int outdegree(dataType x);//出度
    void addEdge(dataType start,dataType end,int wieght);//添加一条边
    void deleteEdge(dataType start,dataType end);//删除一条边
    void printNode(dataType  data,bool isIn);
    void printBase();
};
#pragma 公有函数声明开始
void Graph::init(int vertexNum, int edgeNum){
    this->vertexNum = vertexNum;
    this->edgeNum = edgeNum;
}
int Graph::locate(dataType x){
    for (int i = 0; i<vertexNum; i++) {
        if(base[i].data == x){
            return i;
        }
    }
    return -1;
}
void Graph::create(){
    cout<<"input Graph node data \n";
    for (int i = 0; i<vertexNum; i++) {
        cin>>base[i].data;
        base[i].in = base[i].out = NULL;
    }
    cout<<"input Graph node Start  node and en node:\n";
    dataType start,end;
    int wieght;
    int startPosition,endPosition;
    node *p;
    
    for (int i = 0; i<edgeNum; i++) {
        cout<<"input edge start and end and wieght:\n";
        cin>>start>>end>>wieght;
        startPosition = locate(start);
        endPosition = locate(end);
        p = new node;
        p->info = wieght;
        p->tail = startPosition;
        p->head = endPosition;
        
        p->tailNode = base[startPosition].out;
        base[startPosition].out = p;
        p->headNode= base[endPosition].in;
        base[endPosition].in = p;
        
    }
    cout<<"create finish\n";
}
int  Graph::indegree(dataType x){
    int count = 0;
    node*p =base[ locate(x) ].in;
    while (p != NULL) {
        count++;
        p = p->headNode;
    }
    
    return count;
}
int Graph::outdegree(dataType x){
    int count = 0;
    node*p = base[locate(x)].out;
    while ( p != NULL) {
        count++;
        p = p->tailNode;
    }
    return count;
}
void  Graph::addEdge(dataType start, dataType end, int wieght){
    int startPosition = locate(start);
    int endPostion = locate(end);
    if(startPosition == -1){//返回值为-1，说明这个结点还没有在数组中，先是要添加，然后顶点数+1；边数+1；
        base[vertexNum].data = start;
        base[vertexNum].in = base[vertexNum].out = NULL;
        init(vertexNum+1, edgeNum+1);
    }
    if(endPostion == -1){
        base[vertexNum].data = end;
        base[vertexNum].in = base[vertexNum].out = NULL;
        init(vertexNum+1, edgeNum+1);
    }
    if(startPosition == -1 && endPostion == -1){
        //        两个顶点都没有在数组中，那添加之后顶点个数+2.边数+1；
        base[vertexNum].data = start;
        base[vertexNum].in = base[vertexNum].out = NULL;
        
        base[vertexNum].data = end;
        base[vertexNum].in = base[vertexNum].out = NULL;
        init(vertexNum+2, edgeNum+1);
    }
    
    node *p = new node;
    p->info = wieght;
    p->tail = startPosition;
    p->head = vertexNum-1;
    cout<<"addNode"<<p->tail<<" "<<p->head<<"\n";
    
    p->tailNode = base[startPosition].out;
    base[startPosition].out = p;
    p->headNode = base[endPostion].in;
    base[endPostion].in = p;
}

void Graph::deleteEdge(dataType  start , dataType end){
    int startPostion = locate(start);
    int endPostion = locate(end);
    if(startPostion == -1 || endPostion == -1){
        cout<<"can't not find edge\n";
        return;
    }
    node *nout = base[startPostion].out;
    node  *Hnout = base[startPostion].out;
    
    cout<<nout->tail<<" "<<nout->head<<endl;
    node *nin = base[endPostion].in;
    node *Hnin = base[endPostion].in;
    int num = 0;
    while (nout != NULL) {
        cout<<"+++++++++++"<<base[nout->tail].data<<",."<<base[nout->head].data<<endl;
        if(num == 0 && nout->tail == startPostion && nout->head == endPostion){
            cout<<"if"<<nout->tail<<nout->head<<endl;
            base[startPostion].out = nout->tailNode;
            Hnout = nout;
            nout = nout->tailNode;
            continue;
        }
         if(nout->tail == startPostion && nout->head == endPostion){
            cout<<"else if"<<nout->tail<<nout->head<<endl;
            Hnout->tailNode = nout->tailNode;
            break;
        }
        num++;
        Hnout = nout;
//        cout<<nout->tail<<","<<nout->head<<endl;
        nout = nout->tailNode;
    }
     num=0;
    while (nin != NULL) {
        cout<<"in+++++++++++"<<base[nin->tail].data<<".,"<<base[nin->head].data<<endl;
        if(num == 0 && nin->tail == startPostion && nin->head  == endPostion){
            base[endPostion].in = nin->headNode;
            Hnin = nin;
            nin = nin->headNode;
            continue;
        }
        else if(nin->tail == startPostion && nin->head  == endPostion ){
            Hnin->headNode = nin->headNode;
            delete nin;
            break;
        }
        num++;
        Hnin = nin;
        nin = nin->headNode;
    }

}


void Graph::printNode(dataType data,bool isIn){
    cout<<"printNode++++++++++++++++++++++++++++++++\n";
    int position = locate(data);
    if(position == -1){
        cout<<"input error\n";
        return;
    }
    node *p = nullptr;
    isIn?(p = base[position].in):(base[position].out);
        while (p!= NULL) {
             cout<<"node start:"<<base[p->tail].data<<"\t"<<"node end"<<base[p->head].data<<"\t"<<"node weight:"<<p->info<<"\n";
             isIn? p = p->headNode:p = p->tailNode;
        }
    cout<<"printNode_________________________________\n";
}
void Graph::printBase(){
    cout<<"PrintBse +++++++++++++++++++++++++++++++++++++\n";
    for (int i = 0; i<vertexNum; i++) {
        cout<<"base:"<<base[i].data<<endl;
    }
    cout<<"vertexNum:"<<this->vertexNum<<endl;
    cout<<"edgeNum:"<<this->edgeNum<<endl;
    cout<<"PrintBse _____________________________________\n";
}


#pragma 公有函数声明结束
int main (){
    Graph h;
    h.init(4, 7);
    h.create();
    h.printBase();
    cout<<"入度"<< h.indegree('b')<<endl;
    cout<<"出度"<< h.outdegree('b')<<endl;
    h.printNode('b', true);
    h.addEdge('b', 'e', 1);
     cout<<"出度"<< h.outdegree('b')<<endl;
    h.deleteEdge('b', 'e');
    cout<<"出度"<< h.outdegree('b')<<endl;
    h.printBase();
    cout<<"入度"<< h.indegree('a')<<endl;
    cout<<"出度"<< h.outdegree('a')<<endl;
    h.deleteEdge('a', 'b');
     cout<<"出度"<<h.outdegree('a');
    cout<<"入度"<<h.indegree('b');
    return 1;
}
